package kyssion.leetcode.num1_50;

/**
 * 编写一个程序，通过已填充的空格来解决数独问题。
 * <p>
 * 一个数独的解法需遵循如下规则：
 * <p>
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
 * 空白格用 '.' 表示。
 * <p>
 * <p>
 * <p>
 * 一个数独。
 * <p>
 * <p>
 * <p>
 * 答案被标成红色。
 * <p>
 * Note:
 * <p>
 * 给定的数独序列只包含数字 1-9 和字符 '.' 。
 * 你可以假设给定的数独只有唯一解。
 * 给定数独永远是 9x9 形式的。
 */
public class code37_解数独 {
    boolean[][] row = new boolean[9][9];
    boolean[][] col = new boolean[9][9];
    boolean[][] block = new boolean[9][9];

    public static void main(String[] args) {
        char[][] item = new char[][]{
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};

        for (int a = 0; a < 9; a++) {
            for (int b = 0; b < 9; b++) {
                System.out.print(" " + item[a][b]);
            }
            System.out.println();
        }

        System.out.println();

        new code37_解数独().solveSudoku(item);
        for (int a = 0; a < 9; a++) {
            for (int b = 0; b < 9; b++) {
                System.out.print(" " + item[a][b]);
            }
            System.out.println();
        }
        System.out.println();
    }

    /**
     * 这里就一个点处理的很好,二维数组一维化
     * @param board
     */
    public void solveSudoku(char[][] board) {
        for (int a = 0; a < 9; a++) {
            int num = -1;
            for (int b = 0; b < 9; b++) {
                if (board[a][b] != '.') {
                    num = board[a][b] - '0';
                    row[a][num - 1] = col[b][num - 1] = block[a / 3 * 3 + b / 3][num - 1] = true;
                }
            }
        }
        ans(board, 0);
    }

    public boolean ans(char[][] board, int index) {
        if (index >= 81) {
            return true;
        }
        while (index < 81) {
            int i = index / 9;
            int j = index - i * 9;
            if (board[i][j] == '.') {
                for (int k = 1; k <= 9; k++) {
                    if (!(row[i][k - 1] || col[j][k - 1] || block[i / 3 * 3 + j / 3][k - 1])) {
                        row[i][k - 1] = col[j][k - 1] = block[i / 3 * 3 + j / 3][k - 1] = true;
                        char iii = (char) ('0' + k);
                        board[i][j] = (char) ('0' + k);
                        if (ans(board, index + 1)) {
                            return true;
                        }
                        row[i][k - 1] = col[j][k - 1] = block[i / 3 * 3 + j / 3][k - 1] = false;
                        board[i][j] = '.';
                    }
                }
                return false;
            }
            index++;
        }
        return true;
    }
}
